<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4392：[Usaco2015 dec]Counting Haybales</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2015 dec]Counting Haybales</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2015 dec]Counting Haybales</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2015 dec]Counting Haybales                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has made the project perhaps more complicated than necessary. Please help him follow his instructions to complete the farm upgrade.<br />
<br />
FJ's farm consists of NN fields in a row, conveniently numbered 1&hellip;N1&hellip;N. In each field there can be any number of haybales. Farmer John's instructions contain three types of entries:<br />
<br />
1) Given a contiguous interval of fields, add a new haybale to each field.<br />
<br />
2) Given a contiguous interval of fields, determine the minimum number of haybales in a field within that interval.<br />
<br />
3) Given a contiguous interval of fields, count the total number of haybales inside that interval.</p>
<p>农夫约翰打算重修他的农场。他有 N 块土地，连续排列成一行，标号为 1&hellip;N。在每块土地上有任意数量的草堆。他可以发出三种指令：<br />
1) 对一个连续区间的土地，每块土地增加相同数量的草堆。<br />
2) 对一个连续区间的土地，输出其中最少的草堆数量。<br />
3) 对一个连续区间的土地，输出草堆数量总数。<br />
<br />
第一行两个正整数，N (1&le;N&le;200,000) 和 Q (1&le;Q&le;100,000)。<br />
下一行是N个非负整数，最大100,000，表示每块土地上有多少个草堆。<br />
以下Q行，每行一单个大写字母开头(M，P或S)，空格后跟随两个正整数 A 和 B (1&le;A&le;B&le;N), 或者三个正整数 A, B, 和 C (1&le;A&le;B&le;N; 1&le;C&le;100,000)。当且仅当第一个字母是 P 时，是三个正整数。<br />
当该字母是M，输出区间A&hellip;B的最小草堆数。<br />
当该字母是P，在区间A&hellip;B，每块土地增加C堆草。<br />
当该字母是M，输出区间A&hellip;B的草堆数之和。<br />
<br />
每行一个数字，用于响应'M' 或 'S' 命令。</p>
<p></p></p><hr/><h3>输入格式</h3><p><p>The first line contains two positive integers, N (1&le;N&le;200,000) and Q (1&le;Q&le;100,000).<br />
<br />
The next line contains N nonnegative integers, each at most 100,000, indicating how many haybales are initially in each field.<br />
<br />
Each  of the next Q lines contains a single uppercase letter, either M, P or  S, followed by either two positive integers AA and BB (1&le;A&le;B&le;N), or  three positive integers AA, BB, and CC (1&le;A&le;B&le;N; 1&le;C&le;100,000). There  will be three positive integers if and only if the uppercase letter is  P.<br />
<br />
If the letter is M, print the minimum number of haybales in the interval of fields from A&hellip;B.<br />
<br />
If the letter is P, put C new haybales in each field in the interval of fields from A&hellip;B.<br />
<br />
If the letter is S, print the total number of haybales found within interval of fields from A&hellip;B.</p></p><hr/><h3>输出格式</h3><p><p>A line in the output should appear in response to every 'M' or 'S' entry in FJ's instructions.</p></p><hr/><h3>样例输入</h3><pre>4 5
3 1 2 4
M 3 4
S 1 3
P 2 3 1
M 3 4
S 1 3</pre><hr/><h3>样例输出</h3><pre>2
6
3
8</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Platinum鸣谢Claris提供译文</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4392" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4392" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>